package com.zang.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ZVerify
 * @since 2022/11/23 10:44
 * @see <a href="https://leetcode.cn/problems/partition-labels/discussion/">...</a>
 **/
public class 划分字母区间 {

    public List<Integer> partitionLabels(String s) {

        List<Integer> list = new ArrayList<>();
        int[] map = new int[26];// i代表字母，map[i]代表
        // 将最后一次出现的坐标放到map中
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)-'a'] = i;
        }

        // 当前范围内的最远坐标
        int index = 0;
        // 在进行统计的时候使用去计算当前范围内的字母数量
        int last = -1;

        for (int i = 0; i < s.length(); i++) {
            // 对比当前的区域范围最大坐标和还没有到达最远坐标的距离的元素最远坐标
            // 如果比当前区域最大坐标远的话就更新
            index = Math.max(index, map[s.charAt(i) - 'a']);
            // 到达当前最远范围将范围内的所有数据统计然后更新开始点
            if (i == index) {
                list.add(i-last);
                last = i;
            }
        }
        return list;
    }
}
